/*
 * @Author: 缄默
 * @Date: 2021-11-08 19:12:13
 * @LastEditors: 缄默
 * @LastEditTime: 2021-11-11 19:14:23
 */

//在二叉树中找到累加和为为指定值的最长路径长度

#include <iostream>
#include <vector>
#include <map>

using namespace std;

struct TreeNode {
    int value;
    TreeNode* left;
    TreeNode* right;
    TreeNode (int x) : value(x), left(nullptr), right(nullptr) { }
    
};

int getMaxLength(TreeNode* head, int sum);

TreeNode* buildTree(vector<int>& pre, vector<int>& inOrder, int index, int left, int right);

int preOrder(TreeNode* head, int sum, int preSum, int level, int maxLen, map<int, int>& sumMap);

int main() {
    vector<int> preOrder({3, 9, 20, 15, 7});
    vector<int> inOrder({9, 3, 15, 20, 7});
    TreeNode* head = buildTree(preOrder, inOrder, 0, 0, preOrder.size() - 1);
    cout << getMaxLength(head, 3) << endl;
    return 0;
}

TreeNode* buildTree(vector<int>& pre, vector<int>& inOrder, int index, int left, int right) {
    if (left > right)
        return nullptr;
    TreeNode* head = new TreeNode(pre[index]);
    int i = left;
    while (i < right && pre[index] != inOrder[i]) {
        i++;
    }
    head->left = buildTree(pre, inOrder, index + 1, left, i - 1);
    //根节点的位置加上左子树的长度 在加1就是子树根节点的位置
    head->right = buildTree(pre, inOrder, index + i - left + 1, i + 1, right);
    return head;
}

int getMaxLength(TreeNode* head, int sum) {
    map<int, int> sumMap;
    sumMap[0] = 0;
    return preOrder(head, sum, 0, 1, 0, sumMap);
}

int preOrder(TreeNode* head, int sum, int preSum, int level, int maxLen, map<int, int>& sumMap) {
    if (head == nullptr) {
        return maxLen;
    }
    int curSum = preSum + head->value;
    if (sumMap.count(curSum) == 0) {
        sumMap[curSum] = level;
    }
    if (sumMap.count(curSum - sum) == 1) {
        maxLen = level > maxLen ? level : maxLen;
    } 
    maxLen = preOrder(head->left, sum, curSum, level + 1, maxLen, sumMap);
    maxLen = preOrder(head->right, sum, curSum, level + 1, maxLen, sumMap);
    if (level == sumMap[curSum]) {
        if (sumMap.erase(curSum)) { }
    }
    return maxLen;

}
